package unionfindset;

import java.util.Arrays;

/**
 * @Author 12629
 * @Description：
 */
public class UnionFindSet {
    public int[] elem;

    public UnionFindSet(int n) {
        this.elem = new int[n];
        Arrays.fill(elem,-1);
    }

    /**
     * 查找数据x 的根节点
     * @param x
     * @return 下标
     */
    public int findRoot(int x) {
        if(x < 0) {
            throw new IndexOutOfBoundsException("下标不合法，是负数");
        }
        while (elem[x] >= 0 ) {
            x = elem[x];//1  0
        }
        return x;
    }

    /**
     * 查询x1 和 x2 是不是同一个集合
     * @param x1
     * @param x2
     * @return
     */
    public boolean isSameUnionFindSet(int x1,int x2) {
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if(index1 == index2) {
            return true;
        }
        return false;
    }

    /**
     * 这是合并操作
     * @param x1
     * @param x2
     */
    public void union(int x1,int x2) {
        int index1 = findRoot(x1);
        int index2 = findRoot(x2);
        if(index1 == index2) {
            return;
        }
        elem[index1] = elem[index1] + elem[index2];
        elem[index2] = index1;
    }

    public int getCount() {
        int count = 0;
        for (int x : elem) {
            if(x <  0) {
                count++;
            }
        }
        return count;
    }

    public void print() {
        for (int x : elem) {
           System.out.print(x+" ");
        }
        System.out.println();
    }

    //省份的数量
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFindSet ufs = new UnionFindSet(n);
        for(int i = 0;i < isConnected.length;i++) {
            for(int j = 0;j < isConnected[i].length;j++) {
                if(isConnected[i][j] == 1) {
                    ufs.union(i,j);
                }
            }
        }
        return ufs.getCount();
    }

    //等式的满足性
    public boolean equationsPossible(String[] equations) {
        UnionFindSet ufs = new UnionFindSet(26);
        for(int i = 0; i < equations.length;i++) {
            if(equations[i].charAt(1) == '=') {
                ufs.union(equations[i].charAt(0)-'a',equations[i].charAt(3)-'a');
            }
        }
        for(int i = 0; i < equations.length;i++) {
            if(equations[i].charAt(1) == '!') {
                int index1 = ufs.findRoot(equations[i].charAt(0)-'a');
                int index2 = ufs.findRoot(equations[i].charAt(3)-'a');
                if(index1 == index2) return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String[] str = {"a==b","b!=a"};
        //equationsPossible(str);
    }

    //亲戚题
    public static void main2(String[] args) {
        int n = 10;
        int m = 3;
        int p = 2;

        UnionFindSet unionFindSet = new UnionFindSet(n);

        System.out.println("合并：0和6：");
        unionFindSet.union(0,6);
        unionFindSet.union(0,1);
        System.out.println("合并：3和7：");
        unionFindSet.union(3,7);
        System.out.println("合并：4和8：");
        unionFindSet.union(4,8);

        System.out.println("以下是不是亲戚：");
        boolean flg = unionFindSet.isSameUnionFindSet(1,8);
        if(flg) {
            System.out.println("是亲戚！");
        }else {
            System.out.println("不是亲戚！");
        }
        System.out.println("当亲的亲戚关系 "+unionFindSet.getCount()+" 对！");
    }

    public static void main1(String[] args) {
        UnionFindSet unionFindSet = new UnionFindSet(10);
        System.out.println("合并：0和6：");
        unionFindSet.union(0,6);
        System.out.println("合并：0和7：");
        unionFindSet.union(0,7);
        System.out.println("合并：0和8：");
        unionFindSet.union(0,8);

        System.out.println("合并：1和4：");
        unionFindSet.union(1,4);
        System.out.println("合并：1和9：");
        unionFindSet.union(1,9);
        System.out.println("合并：2和3：");
        unionFindSet.union(2,3);

        System.out.println("合并：2和5：");
        unionFindSet.union(2,5);

        unionFindSet.print();

        System.out.println("合并：8和1：");
        unionFindSet.union(8,1);

        unionFindSet.print();

        System.out.println("查找是不是同一个集合");
        System.out.println(unionFindSet.isSameUnionFindSet(6, 9));
        System.out.println(unionFindSet.isSameUnionFindSet(8, 2));

    }
}
